#include<string>
using namespace std;
class Solution
{
public:
    void my_reverse(string &s, int i, size_t j = string::npos)
    {
        if (j == string::npos)
            j = s.size();
        --j;
        while (i < j)
        {
            swap(s[i++], s[j--]);
        }
    }
    string reverseWords(string s)
    {
        // O(1)空间O(N)时间
        // 移除空格
        int i = 0, j = 0;
        while (j < s.size())
        {
            if (s[j] == ' ')
            {
                j++;
                continue;
            }
            while (j < s.size() && s[j] != ' ')
            {
                s[i++] = s[j++];
            }
            if (j < s.size())
                s[i++] = s[j++];
        }
        s.erase(i);
        if (s.back() == ' ')
            s.pop_back();
        // 整体反转
        my_reverse(s, 0);
        // 每个单词反转
        i = 0, j = 0;
        while (1)
        {
            j = s.find(' ', i);
            my_reverse(s, i, j);
            if (j == string::npos)
                break;
            i = j + 1;
        }
        return s;
    }
};